Binary Search Tree Roadmap

Goal: maintain order with fast search / insert / delete. Shape controls comparisons.

Prototype Shape

Explore

Click any node. Trace root → node path. Which ordering rule must always hold so pruning works?

40 20 60 10 30 50 70
Click a node to highlight its search path.

Guiding Questions

  • How is ordering enforced everywhere?
  • Why does the path discard many keys?
  • What input order ruins height?
  • How do we emit sorted output?

Core Concerns (Detailed Preview)

  • InvariantEvery node partitions key space: left subtree keys all less; right subtree keys all greater; holds recursively.
  • Search PathSingle comparison decides next branch; cost proportional to height h.
  • InsertionSimulate search for key; first null hit becomes leaf; invariant preserved by path choice.
  • Deletion0-child: remove. 1-child: splice child up. 2-children: swap with inorder successor (min of right) or predecessor then reduce to simpler case.
  • TraversalsInorder = sorted. Preorder = shape capture (useful for reconstruction). Postorder = safe free/remove. Level-order = breadth insight.
  • Height & ComplexityOps are O(h). Ideal random / balanced h ≈ log₂ n; worst sequential inserts h = n (degenerates to list).
  • Balance PressureSkew growth increases cost; motivates rotations & self-balancing variants (AVL, Red-Black) later.
  • Duplicates PolicyDecide: reject, count, or side-bias (e.g., duplicates to right). Must be explicit for correctness.
  • Memory LayoutPointer-rich nodes enable flexible growth; cache locality poorer than arrays but update costs cheaper than shifting.
  • Order Statistics (Preview)Augment with subtree sizes to support k-th element & rank queries in O(h).

Next: formal definition slide.